//Given a string s representing an expression, implement a basic calculator to e
//valuate it. 
//
// 
// Example 1: 
//
// 
//Input: s = "1 + 1"
//Output: 2
// 
//
// Example 2: 
//
// 
//Input: s = " 2-1 + 2 "
//Output: 3
// 
//
// Example 3: 
//
// 
//Input: s = "(1+(4+5+2)-3)+(6+8)"
//Output: 23
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 3 * 105 
// s consists of digits, '+', '-', '(', ')', and ' '. 
// s represents a valid expression. 
// 
// Related Topics 栈 数学 
// 👍 558 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Basic Calculator
class P224BasicCalculator {
    public static void main(String[] args) {
        Solution solution = new P224BasicCalculator().new Solution();
        // TO TEST
        System.out.println(solution.calculate("-((-4+5+2)+3)+(6+8)"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        String min = "+-";
        String max = "*/";
        String op = "+-*/()";

        public int calculate(String s) {
            if (s == null || s.equals("")) {
                return 0;
            }
            if (s.startsWith("+") || s.startsWith("-")) {
                s = "0" + s;
            }
            char[] chars = s.toCharArray();
            Stack<String> stackOp = new Stack<>();
            Deque<String> stackNum = new ArrayDeque<>();

            //3*(2-1)-3*2
            //3 2 1 * - 3 2 * -

            StringBuilder num = new StringBuilder();
            for (int i = 0; i < chars.length; i++) {
                char ch = chars[i];
                String str = String.valueOf(ch).trim();
                if (str.length() == 0) {
                    continue;
                }
                if (op.contains(str)) {
                    //数字结束
                    if (min.contains(str) && (i == 0 || !stackOp.isEmpty() && stackOp.peek().equals("(") &&
                            (stackNum.isEmpty()||(!stackNum.isEmpty() && !op.contains(stackNum.peek()))) &&
                            !op.contains(String.valueOf(chars[i + 1])) && num.length() == 0)) {

                        num.append(ch);
                        continue;
                    }
                    if (num.length() != 0) {
                        stackNum.push(num.toString());
                    }
                    if (str.equals("(") || stackOp.isEmpty()) {
                        stackOp.push(str);
                    } else if (str.equals(")")) {
                        while (!stackOp.peek().equals("(")) {
                            stackNum.push(stackOp.pop());
                        }
                        stackOp.pop();
                    } else if (stackOp.peek().equals("(")) {
                        stackOp.push(str);
                    } else {
                        while (!stackOp.isEmpty() && opCompare(stackOp.peek(), str)) {
                            stackNum.push(stackOp.pop());
                        }
                        stackOp.push(str);

                    }
                    num = new StringBuilder();
                } else {
                    num.append(str);
                }
            }
            if (num.length() != 0) {
                stackNum.push(num.toString());
            }
            while (!stackOp.isEmpty()) {
                stackNum.push(stackOp.pop());
            }
            return evalRPN(stackNum);
        }

        public boolean opCompare(String a1, String a2) {
            if (max.contains(a2) && min.contains(a1)) {
                return false;
            }
            return true;
        }

        public int evalRPN(Deque<String> tokens) {
            Stack<String> stack = new Stack<>();
            if (tokens == null || tokens.isEmpty()) {
                return 0;
            }
            while (!tokens.isEmpty()) {
                String token = tokens.pollLast();
                if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                    if (!stack.isEmpty()) {
                        int back = Integer.parseInt(stack.pop());
                        int front = Integer.parseInt(stack.pop());
                        int val = 0;
                        switch (token) {
                            case "+":
                                val = front + back;
                                break;
                            case "-":
                                val = front - back;
                                break;
                            case "*":
                                val = front * back;
                                break;
                            case "/":
                                val = front / back;
                                break;
                        }
                        stack.push(String.valueOf(val));
                    } else {
                        stack.push(token);
                    }
                } else {
                    stack.push(token);
                }
            }
            return Integer.parseInt(stack.pop());
        }
    }
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        // sign 代表正负
        int sign = 1, res = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                int cur = ch - '0';
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
                    cur = cur * 10 + s.charAt(++i) - '0';
                res = res + sign * cur;
            } else if (ch == '+') {
                sign = 1;
            } else if (ch == '-') {
                sign = -1;
            } else if (ch == '(') {
                stack.push(res);
                res = 0;
                stack.push(sign);
                sign = 1;
            } else if (ch == ')') {
                res = stack.pop() * res + stack.pop();
            }
        }
        return res;
    }

//leetcode submit region end(Prohibit modification and deletion)
}